#include "sqlist.h"
#include <iostream>
#include <cmath>
using namespace std;

void dataStruct::createList(SqList*& L, ElementType a[], int n)
{
	L = new SqList;
	for (size_t i = 0; i < size_t(fmin(n, SQLISTMAXSIZE)); i++)
	{
		L->data[i] = a[i];
	}

	L->length = fmin(n, SQLISTMAXSIZE);
}

void dataStruct::initList(SqList*& L)
{
	L = new SqList;
	L->length = 0;
}

void dataStruct::destoryList(SqList*& L)
{
	delete L;
}

bool dataStruct::listEmpty(SqList* L)
{
	return !(L->length);
}

int dataStruct::listLength(SqList* L)
{
	return L->length;
}

void dataStruct::dispList(SqList* L)
{
	for (size_t i = 0; i < L->length; i++)
	{
		if (i % 10 == 0 && i != 0)
		{
			cout << endl;
		}
		cout << L->data[i] << " ";
		
	}

	cout << endl;
}

bool dataStruct::getElem(SqList* L, size_t i, ElementType& e)
{
	if (i < 0 || i > L->length)
	{
		return false;
	}

	e = L->data[i - 1];
	return true;
}

int dataStruct::locateElem(SqList* L, ElementType e)
{
	for (size_t i = 0; i < L->length; i++)
	{
		if (L->data[i] == e)
		{
			return i + 1;
		}
	}

	return 0;
}

bool dataStruct::listInsert(SqList*& L, size_t i, ElementType e)
{
	if (i < 1 || i > fmin(L->length + 1, SQLISTMAXSIZE))
	{
		return false;
	}

	size_t k = L->length;
	i--;
	for (; k > i; k--)
	{
		L->data[k] = L->data[k - 1];
	}

	L->data[i] = e;
	L->length = L->length + 1;
	return true;
}

bool dataStruct::listDelete(SqList*& L, size_t i, ElementType& e)
{
	if (i < 1 || i > L->length)
	{
		return false;
	}

	e = L->data[i - 1];
	for (size_t k = i - 1; k < L->length - 1; k++)
	{
		L->data[k] = L->data[k + 1];
	}

	L->length--;
	return false;
}

void dataStruct::delNode(SqList*& L, ElementType x)
{
	int curIdx = 0;
	int num = 0;
	for (size_t i = 0; i < L->length; i++)
	{
		if (x == L->data[i])
		{
			num++;
		}
		else
		{
			L->data[curIdx] = L->data[i];
			curIdx++;
		}
	}

	L->length -= num;
}

int dataStruct::partition(SqList*& L)
{
	int i = 0;
	int j = L->length - 1;
	while (i < j)
	{
		while (i < j && L->data[i] <= L->data[0])
		{
			i++;
		}
		while (i < j && L->data[j] > L->data[0])
		{
			j--;
		}

		ElementType temp = L->data[i];
		L->data[i] = L->data[j];
		L->data[j] = temp;
	}

	if (i < j)
	{
		ElementType temp = L->data[0];
		L->data[0] = L->data[j];
		L->data[j] = temp;
	}
	
	return j;
}

void dataStruct::move(SqList*& L)
{
	int i = 0;
	int j = L->length - 1;
	while (i < j)
	{
		while (i < j && L->data[i] % 2 == 0)
		{
			i++;
		}
		while (j > i && L->data[i] % 2 == 1)
		{
			j--;
		}

		if (i < j)
		{
			ElementType temp = L->data[i];
			L->data[i] = L->data[j];
			L->data[j] = temp;
		}
	}
}
